/**
 * describe:
 *
 * @author chaP
 * @date 2019/04/10
 */
package CodingTest.AC20190410;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode - 39
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

 candidates 中的数字可以无限制重复被选取。

 说明：

 所有数字（包括 target）都是正整数。
 解集不能包含重复的组合。
 示例 1:

 输入: candidates = [2,3,6,7], target = 7,
 所求解集为:
 [
 [7],
 [2,2,3]
 ]
 示例 2:

 输入: candidates = [2,3,5], target = 8,
 所求解集为:
 [
 [2,2,2,2],
 [2,3,3],
 [3,5]
 ]
 */
public class combinationSum {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> combinationSum(int[] candidates, int target){
            List<Integer> list = new ArrayList<Integer>();
            helper(candidates,target,0,list);
            return result;
    }
    public void helper(int[] candidates,int target,int start,List<Integer> list){
        if(target < 0) return ;
        else if(target == 0) result.add(new ArrayList<>(list));
        else {
            for(int i =start;i<candidates.length;i++){
                list.add(candidates[i]);
                helper(candidates,target-candidates[i],i,list);
                list.remove(list.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        int[] candidates = {2,3,5};
        int target = 8;
        combinationSum cs = new combinationSum();
        System.out.println(cs.combinationSum(candidates,target));
    }
}
